DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2023.54

Connected Vertex Cover on AT-Free Graphs

Authors: Joydeep Mukherjee and Tamojit Saha

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract

Asteroidal Triple (AT) in a graph is an independent set of three vertices such that every pair of them has a path between them avoiding the neighbourhood of the third. A graph is called AT-free if it does not contain any asteroidal triple. A connected vertex cover of a graph is a subset of its vertices which contains at least one endpoint of each edge and induces a connected subgraph. Settling the complexity of computing a minimum connected vertex cover in an AT-free graph was mentioned as an open problem in Escoffier et al. [Escoffier et al., 2010]. In this paper we answer the question by presenting an exact polynomial time algorithm for computing a minimum connected vertex cover problem on AT-free graphs.

Cite as

Joydeep Mukherjee and Tamojit Saha. Connected Vertex Cover on AT-Free Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 54:1-54:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{mukherjee_et_al:LIPIcs.ISAAC.2023.54,
  author =	{Mukherjee, Joydeep and Saha, Tamojit},
  title =	{{Connected Vertex Cover on AT-Free Graphs}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{54:1--54:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.54},
  URN =		{urn:nbn:de:0030-drops-193566},
  doi =		{10.4230/LIPIcs.ISAAC.2023.54},
  annote =	{Keywords: Graph Algorithm, AT-free graphs, Connected Vertex Cover, Optimization}
}

Search Results

Documents authored by Mukherjee, Joydeep

Connected Vertex Cover on AT-Free Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message